succinct non-interactive argument of knowledge

Definition

A succinct preprocessing NARK is a triple $(S,P,V)$:

• $S(C)$, public parameters $(pp,vp)$ for prover and verifier
• $P(pp,x,w)$, short proof $\pi$
  • $\operatorname{len}(\pi) = O_\lambda(\operatorname{polylog}(|C|))$
• $V(vp, x, \pi)$, fast to verify
  • $\operatorname{time}(V) = O_\lambda(|x|, \operatorname{polylog}(|C|))$

Construction (PCP-based SNARK)

• recall PCP theorem;
• Use Fiat-Shamir transform to make the proof non-interactive
• #incomplete
• (impractical as not efficient)

See also

• SNARGs
• (preprocessing) NARK
• NIZK
• proof system

References

1. https://cs251.stanford.edu/lectures/lecture15.pdf
2. https://rdi.berkeley.edu/zkp-course/assets/Lecture2-2023.pdf
3. https://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof
4. https://crypto.stackexchange.com/questions/74382/zk-snarks-vs-zk-starks-vs-bulletproofs-definitions
5. https://a16zcrypto.com/posts/article/snark-security-and-performance/
6. https://www.cryptologie.net/posts/theyre-all-snarks/
7. https://zhuanlan.zhihu.com/p/714666313
8. https://zhuanlan.zhihu.com/p/150246147